package com.ting.test.algorithms.链表;

/**
 * 将单向链表按某值划分成左边小、中间相等、右边大的形式
 * 思路:
 * 分成小、中、大三部分，再把各个部分之间串起来（面试用）
 */
public class 链表分区排列解法2 {
    public static void main(String[] args) {
        SingleNode head1 = new SingleNode(7);
        head1.next = new SingleNode(9);
        head1.next.next = new SingleNode(1);
        head1.next.next.next = new SingleNode(8);
        head1.next.next.next.next = new SingleNode(5);
        head1.next.next.next.next.next = new SingleNode(2);
        head1.next.next.next.next.next.next = new SingleNode(5);
        printLinkedList(head1);
        // head1 = listPartition1(head1, 4);
        head1 = sort(head1, 5);
        printLinkedList(head1);

    }

    public static void printLinkedList(SingleNode node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    private static SingleNode sort(SingleNode head, int target) {
        if (null == head || head.next == null) {
            return head;
        }

        SingleNode sH = null;//表示小于目标节点的区域的头指针
        SingleNode sT = null;//表示小于目标节点的区域的尾指针
        SingleNode eH = null;//表示等于目标节点的区域的头指针
        SingleNode eT = null;//表示等于目标节点的区域的尾指针
        SingleNode mH = null;//表示等大于目标节点的区域的头指针
        SingleNode mT = null;//表示等大于目标节点的区域的尾指针


        SingleNode node;
        do {
            node = head.next;//将当前节点的下一个节点赋值给node
            head.next = null;//这两句其实就是在把当前节点从链表中摘出来
            //如果当前节点值 小于target 则放入小于目标区域
            if (head.getValue() < target) {
                if (sH == null) {
                    //首次进数据时，头尾指针均指向同一个节点
                    sH = head;
                    sT = head;
                } else {
                    //采用尾插法，保证链表数据的稳定性
                    sT.next = head;
                    sT = head;
                }

            } else if (head.getValue() == target) {
                //如果是等于区域
                if (eH == null) {
                    eH = head;
                    eT = head;
                } else {
                    eT.next = head;
                    eT = head;
                }
            } else {
                // 如果是大于区域
                if (mH == null) {
                    mH = head;
                    mT = head;
                } else {
                    mT.next = head;
                    mT = head;
                }

            }

            head = node;
        } while (head != null);

        //准备汇总
        //如果小于区域不为空
        if (sT != null) {
            // 判断 如果小于区域不为空，则考虑等于区域是否为空，
            //如果等于区域不为空，则小于区域的尾节点要连接到等于区域的头节点
            // 同时等于区域的尾节点要连接到大于区域的头结点 不论大于区域是否为空
            if (eT != null) {
                sT.next = eH;
                eT.next = mH;
            } else {
                //如果为空，则无论大于区域是否为空，都可以把小于区域的尾节点链接到大于区域的头结点
                sT.next = mH;
            }
            return sH;
        } else {
            //如果小于区域为空
            if (eT != null) {
                //如果小于区域为空，但等于区域不为空，则把等于区域的尾节点链接到大于区域的头结点
                //且不论大于区域是否为空
                eT.next = mH;
                return eH;
            } else {
                return mH;
            }


        }
    }
}
